class Solution:
    def generateParenthesis(self, n):
        """
        回溯法生成所有有效括号组合
        :param n: 括号对数
        :return: 所有有效组合列表
        """
        res = []
        def backtrack(s, left, right):
            if len(s) == 2 * n:
                res.append(s)
                return
            # 优先添加左括号（剪枝：左括号数不能超过n）
            if left < n:
                backtrack(s + '(', left + 1, right)
            # 添加右括号（剪枝：右括号数不能超过左括号数）
            if right < left:
                backtrack(s + ')', left, right + 1)
        backtrack("", 0, 0)
        return res